﻿// 1010train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <numeric>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <vector>

using namespace std;

/*
第一行输入为N、L
输入
3 2
2
2
3
输出：
1 2
 */
class Solution01
{
public:
    vector<int>checkVerify(double mid, vector<double>& num_vec, int k)
    {
        int v_size = num_vec.size();
        vector<double>pre_sum(v_size + 1);

        pre_sum[0] = 1;
        for (int i=1; i<k; i++)
        {
            pre_sum[i] = pre_sum[i - 1] * (num_vec[i - 1] / mid);
        }

        double min_pre_sum = DBL_MAX;
        int min_pre_pos = -1;
        int curr_pos = -1, curr_len = v_size+1;

        for (int i=k; i<=v_size; i++)
        {
            if (pre_sum[i-k]<min_pre_sum)
            {
                min_pre_sum = pre_sum[i - k];
                min_pre_pos = i - k;
            }
            pre_sum[i] = pre_sum[i - 1] * (num_vec[i - 1] / mid);
            if (pre_sum[i]>min_pre_sum && i-min_pre_pos<curr_len)
            {
                curr_pos = min_pre_pos;
                curr_len = i - min_pre_pos;
            }
	        //
        }
        vector<int>result;
        if (curr_pos==-1)
        {
            return result;
        }
        result = { curr_pos,curr_len };
        return result;
	    //
    }
    Solution01(vector<double>&num_vec, int k)
    {
        double left = *min_element(num_vec.begin(), num_vec.end());
        double max_num = *max_element(num_vec.begin(), num_vec.end());
        double right = max_num + 1;

        int curr_pos = 0, curr_len = 0;
        while (right-left>pow(10,-10))
        {
            double mid = left + (right - left) / 2;
            vector<int>res = checkVerify(mid, num_vec, k);

            if (!res.empty())
            {
                curr_pos = res[0];
                curr_len = res[1];
                //mid小于几何平均值
                //增大
                left = mid;
            }
            else
            {
                right = mid;
            }
	        //
        }
        cout << curr_pos << ' ' << curr_len;
    	//
    }
};

/*
 给定一个m*n的整数阵作为地图，短阵数值为地形高度；
中庸行者选择地图中的任意一点作为起点，尝试往上、下、左、右四个相邻格子移动;
移动时有如下约束：
中庸行者只能上坡或者下坡，不能走到高度相同的点。
不允许连续上坡或者连续下坡，需要交替进行;
每个位置只能经过一次，不能重复行走；
请给出中庸行者在本地图内，能连续移动的最大次数。

输入描述
第一行两个数字，分别为行数和每行的列数
后续数据为矩阵地图内容
矩阵边长范围：[1,8]
地形高度范围：[0,100000]

输出描述
一个整数，代表中庸行者在本地图内，能连续移动的最大次数。

输入
2 2
1 2
4 3
输出
3
3->4->1->2，一共移动3次
 */
class Solution02
{
public:
    int checkDir(int top_val, int curr_val)
    {
        int curr_dir = 0;
        if (curr_val > top_val)
        {
            curr_dir = 1;
        }
        else if (curr_val < top_val)
        {
            curr_dir = -1;
        }
        if (curr_dir == 0) return 0;
        if (!track_v.empty() && curr_dir == track_v.back())
            return 0;

        return curr_dir;
	    //
    }
    
    void backTrack(
        vector<vector<int>>& grid,
		vector<vector<bool>>&checked,
        vector<int>&pos_v,
        int curr_step
    )
    {
        max_step = max(max_step, curr_step);

        int top_val = grid[pos_v[0]][pos_v[1]];
        for (auto&dir_v:DirectionGrid)
        {
            int row = pos_v[0] + dir_v[0];
            int col = pos_v[1] + dir_v[1];

            bool is_row = row >= 0 && row < row_size_;
            bool is_col = col >= 0 && col < col_size_;

            if (!is_row || !is_col) continue;

            bool is_visited = checked[row][col];
            if (is_visited) continue;
            
            int curr_val = grid[row][col];
            int curr_dir = checkDir(top_val, curr_val);
            if (curr_dir!=0)
            {
                //做选择
                checked[row][col] = true;
                track_v.push_back(curr_dir);
                vector<int>pos_v = { row, col };
                backTrack(grid, checked, pos_v, curr_step + 1);
                //撤销选择
                checked[row][col] = false;
                track_v.pop_back();
            }
        	//
        }
	    //
    }
    
    Solution02(vector<vector<int>>&grid, int row_size, int col_size)
    {
        row_size_ = row_size;
        col_size_ = col_size;

        vector<vector<bool>>checked(row_size_, vector<bool>(col_size_,false));
        for (int r=0; r<row_size_; r++)
        {
	        for (int c=0; c<col_size_; c++)
	        {
                //清除
                track_v.clear();

                checked[r][c] = true;
                vector<int>pos_v = { r,c };
                backTrack(grid, checked, pos_v, 0);
                checked[r][c] = false;
		        //
	        }
            //
        }
        cout << max_step;
	    //
    }
private:
    int max_step = 0;
    int row_size_ = 0, col_size_ = 0;
    vector<int>track_v;
    vector<vector<int>>DirectionGrid = {
		{-1,0},{1,0},{0,-1},{0,1}
    };
};


class Union
{
private:
    unordered_map<int, int>parents;

    void addNode(int node)
    {
        parents[node] = node;
    }

    int findParent(int node)
    {
	    while (parents[node]!=node)
	    {
            node = parents[node];
	    }
    }

    void unionNode(int node_x, int node_y)
    {
	    if (findParent(node_x)!=findParent(node_y))
	    {
            parents[findParent(node_x)] = findParent(node_y);
	    }
    }

	//
};


/*
  任务提交者和任务执行者都有编号，任务提交者在给定时刻向工作队列提交任务，任务有执行所需的时间。
 执行者取出任务的即刻加上执行时间即为任务完成的时刻。

 执行者完成任务变为空闲的时刻会从工作队列中取最老的任务执行，
 若这一时刻有多个空闲的执行者，其中优先级最高的会执行这个任务。

 编号小的执行者优先级高。初始状态下所有执行者都空闲。
 工作队列有最大长度限制，当工作队列满而有新的任务需要加入队列时，
 队列中最老的任务会被丢弃。

 特别的，在工作队列满的情况下，当执行者变为空闲的时刻和新的任务提交的时刻相同时，
 队列中最老的任务被取出执行，新的任务加入队列。

输入描述：
输入为两行。
第一行为2N个正整数，代表提交者提交的N个任务的时刻和执行时间。
第一个数字是第一个任务的提交时刻，第二个数字是第一个任务的执行时间，以此类推。
用例保证提交时刻不会重复，任务按提交时刻升序排列。
第二行为两个数字，分别为工作队列的最大长度和执行者的数量。两行的数字都由空格分隔。
N不超过20，数字为不超过1000的正整数。

输出描述：
输出两个数字，分别为最后一个任务执行完成的时刻和被丢弃的任务的数量，数字由空格分隔。

示例1：
输入：
1 3 2 2 3 3
3 2
输出：
7 0
 */
class Solution03
{
public:
    Solution03(vector<vector<int>>&task_vec,int max_size, int exec_size)
    {
        //max_size队列最大长度
        //exec_size执行器长度

        //curr_time下一个任务执行时间/执行器最早结束时间

        int index = 0;
        int task_size = task_vec.size();
        int final_time = 0;
        int reject_count = 0;
        //final_time，执行器里结束最晚的时间

        deque<vector<int>>wait_queue;
        vector<int>exector_v(exec_size);

        while (index<task_size || !wait_queue.empty())
        {
            //curr_time下一个任务执行时间/执行器最早结束时间
            int curr_time = INT_MAX;
            if (index<task_size)
            {
                curr_time = task_vec[index][0];
            }
            for (auto&busy_time:exector_v)
            {
                if (busy_time!=0)
                {
                    curr_time = min(busy_time, curr_time);
                }
            }
            if (curr_time == INT_MAX) break;

            //寻找空闲的执行器
            deque<int>free_queue;
            for (int i=0; i<exec_size; i++)
            {
                if (exector_v[i]<=curr_time)
                {
                    exector_v[i] = 0;
                    free_queue.push_back(i);
                }
	            //
            }
            //队列里的工作任务塞进执行器
            int wait_size = wait_queue.size();
            int free_size = free_queue.size();

            for (int i=0; i<min(wait_size,free_size); i++)
            {
                vector<int>task_v = wait_queue.front();
                wait_queue.pop_front();

                int free_i = free_queue.front();
                free_queue.pop_front();

                exector_v[free_i] = curr_time + task_v[1];
	            //
            }

            //新的任务加入队列
            if (index<task_size && task_vec[index][0]<=curr_time)
            {
                //优先往执行器塞
                if (!free_queue.empty())
                {
                    int free_i = free_queue.front();
                    free_queue.pop_front();

                    exector_v[free_i] = curr_time + task_vec[index][1];
                    index++;
                	//
                }
                else
                {
                    //往等待队列塞
                    if ((int)wait_queue.size() == max_size)
                    {
                        wait_queue.pop_front();
                        reject_count++;
                    }
                    wait_queue.push_back(task_vec[index]);
                    index++;
                }
                //
            }
            //更新最晚结束时间
            for (auto&busy_time:exector_v)
            {
                final_time = max(busy_time, final_time);
            }

	        //
        }

        cout << final_time << ' ' << reject_count;

	    //
    }
};

vector<int>handleSpace(string&str)
{
    vector<int>result;
    stringstream oh_sstream(str);
    string token;

    while (oh_sstream>>token)
    {
        result.push_back(stoi(token));
    }
    return result;
	//
}

int main()
{
	{
        //1 3 2 2 3 3
		//3 2
        string task_str;
        getline(cin, task_str);
        vector<int>num_vec = handleSpace(task_str);
        vector<vector<int>>task_vec;
        for (int i=0; i<int(num_vec.size()); i+=2)
        {
            vector<int>item = { num_vec[i],num_vec[i + 1] };
            task_vec.push_back(item);
        }
        string base_str;
        getline(cin, base_str);
        vector<int>base_v = handleSpace(base_str);
        //最大长度和执行者的数
        int max_size = base_v[0];
        int exec_size = base_v[1];

        Solution03 solu(task_vec, max_size, exec_size);

        return 0;
	}
	{
        int row_size, col_size;
        cin >> row_size >> col_size;

        vector<vector<int>>grid(row_size, vector<int>(col_size));

        for (int r=0; r<row_size; r++)
        {
	        for (int c=0; c<col_size; c++)
	        {
                cin >> grid[r][c];
	        }
        }
        Solution02 solu(grid, row_size, col_size);

        return 0;
	}
    int v_size, k;
    cin >> v_size >> k;

    vector<double>num_vec(v_size);
    for (int i=0; i<v_size; i++)
    {
        cin >> num_vec[i];
    }
    Solution01 solu(num_vec, k);
    return 0;
    //
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
